package day_2022_7_to_8.day48;

import java.util.ArrayList;
import java.util.List;

/**
 * @author haomin
 * @date 2022/08/12 21:57
 **/
public class Day27_2_Num39_CombinationSum {
    class Solution {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> ret = new ArrayList<>();
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            dfs(candidates,0,0,target);
            return res;
        }
        private void dfs(int[] candidates, int sum,int start, int target){
            if(sum == target){
                List<Integer> list = new ArrayList<>(ret);
                if(!res.contains(list)) res.add(list);
                return;
            }else if(sum > target) return;
            for(int i = start;i < candidates.length;i++){
                sum+=candidates[i];ret.add(candidates[i]);
                dfs(candidates,sum,i,target);
                sum-=candidates[i];ret.remove(ret.size()-1);
            }
        }
    }
}